'''
https://leetcode.cn/problems/maximum-width-ramp/
'''
from collections import deque
from typing import List

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        stack = deque([0])          # 小压大.
                                    # 如果某个元素比我小在我左边，那我一定不是最好的左边界，就不入栈
                                    # 最后从右往左收集答案，就可以直接扔了。因为从右往左，这已经是我能收集到最好的右边界了
        for i, num in enumerate(nums):
            if num < nums[stack[-1]]:
                stack.append(i)
        ans = 0
        for right in range(len(nums) - 1, -1, -1):
            while stack and nums[right] >= nums[stack[-1]]:
                left = stack.pop()
                ans = max(ans, right - left)
        return ans


nums = [6,0,8,2,1,5]
print(Solution().maxWidthRamp(nums))